package com.chao.base.struct;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : Rookie
 * @description : lru
 * @date : 2023/10/15
 */
public class LRUCache<K,V> {
    /**
     * 缓存大小
     */
    private final int size;
    /**
     * 缓存表
     */
    private final Map<K,Node<K,V>> cache;
    /**
     * 头节点
     */
    private final Node<K,V> head;
    /**
     * 尾节点
     */
    private final Node<K,V> tail;

    public LRUCache(int size) {
        this.size = size;
        this.cache = new HashMap<>(size);
        // 简化操作，头节点和尾节点不存储数据
        this.head = new Node<>();
        this.tail = new Node<>();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public void put(K key,V val) {
        Node<K, V> node = cache.get(key);
        if (node != null) {
            // 更新其中的值
            node.val = val;
            remove(node);
            addNodeToHead(node);
        } else {
            // 键不存在 需要插入 先判断是否达到阈值
            if (cache.size() >= size) {
                Node<K, V> tailNode = tail.prev;
                remove(tailNode);
                cache.remove(tailNode.key);
            }
            // 创建新的节点
            Node<K, V> newNode = new Node<>(key, val);
            cache.put(key,newNode);
            addNodeToHead(newNode);
        }
    }

    public V get(K k) {
        Node<K, V> node = cache.get(k);
        if (node != null) {
            remove(node);
            addNodeToHead(node);
            return node.val;
        }
        return null;
    }

    public void print() {
        Node<K,V> curr = head;
        while (curr != null) {
            if (curr.val != null) {
                System.out.print(curr.val);
            }
            if (curr.next != null && curr.val != null && curr.next.val != null) {
                System.out.print("->");
            }
            curr = curr.next;
        }
    }

    /**
     * 删除链表节点
     * @param node
     */
    private void remove(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNodeToHead(Node<K,V> node) {
        // 当前节点的后继节点为头节点的后继节点
        node.next = head.next;
        // 原头节点的后继节点前驱为当前节点
        node.next.prev = node;
        // 头节点的后继节点为当前节点
        head.next = node;
        // 当前节点的前驱为头节点
        node.prev = head;
    }

    private void addNodeToTail(Node<K,V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    private static class Node<K,V> {
        private K key;

        private V val;

        private Node<K,V> prev;

        private Node<K,V> next;

        public Node() {}

        public Node(K key,V val) {
            this.key = key;
            this.val = val;
        }

    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache<>(3);
        lruCache.put("A",1);
        lruCache.put("B",2);
        lruCache.put("C",3);
        lruCache.get("B");
        lruCache.put("D",4);
        lruCache.print();
    }
}
